package study.datastructure.order.recursion;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-10-08 18:00
 */

/**
 2024/10/8,
 */

import java.io.PipedReader;

/**
 * 杨辉三角
 * 1
 * 11
 * 121
 * 1331
 * 14641
 * 动态规划
 */
public class PascalTriangle {

    static int element(int i, int j){
        if (j==0||i==j){
            return 1;
        }
        return element(i-1,j-1)+element(i-1,j);
    }

    static void print(int n){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(element(i, j));
            }
            System.out.println();
        }
    }
    static int element1(int[][] triangleCache, int i, int j){
        if (triangleCache[i][j]>0){
            return triangleCache[i][j];
        }
        if (j==0||i==j){
            triangleCache[i][j]=1;
            return 1;
        }
        triangleCache[i][j]=element1(triangleCache,i-1,j-1)+element1(triangleCache,i-1,j);
        return triangleCache[i][j];
    }

    static void print1(int n){
        int [][] triangleCache = new int[n][];
        for (int i = 0; i < n; i++) {
            triangleCache[i]=new int[i+1]; //每行长度不等
            for (int j = 0; j <= i; j++) {
                System.out.print(element1(triangleCache,i, j));
            }
            System.out.println();
        }
    }
    static void print2(int n){
        int [] triangleCache = new int[n];
        for (int i = 0; i < n; i++) {
            createRow(triangleCache,i);//每行长度不等
            for (int j = 0; j <= i; j++) {
                System.out.print(triangleCache[j]);
            }
            System.out.println();
        }
    }

    private static void createRow(int[] row, int i){
        if (i==0){
            row[0]=1;
        }
        for (int j=i;j>0;j--){
            row[j] = row[j-1]+row[j];
        }
    }
    public static void main(String[] args) {
        /*System.out.println(element(4,2)); //6
        print(5);*/
        print1(8);
        System.out.println("=========");
        print2(8);
    }
}
